package com.itheima.sort;

public class A05_QuickSort {
    public static void main(String[] args) {
        /*
快速排序：
第一轮：以θ索引的数字为基准数，确定基准数在数组中正确的位置。
比基准数小的全部在左边，比基准数大的全部在右边。
后面以此类推。
         */
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }

    }

    private static void quickSort(int[] arr, int i, int j) {



        //定义一个基准元素
        int pivot = arr[i];

        //定义开始索引和结束索引
        int start = i;
        int end = j;
        if(end<=start){
            return;
        }
        while(end!=start){
            //从结束索引从后往前找比基准元素小的索引
            while (true){
                if (end <= start || arr[end] < pivot){
                    break;
                }
                end--;
            }

            //从开始索引从前往后找比基准元素大的索引
            while (true) {
                if (end <= start || arr[start] > pivot){
                    break;
                }
                start++;
            }

            //交换开始索引和结束索引所在的元素位置
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end]=temp;
        }

        //将开始索引或结束索引所在的元素与基准索引所在的元素交换
        int temp=arr[i];
        arr[i]=arr[end];
        arr[end]=temp;
        //对基准数左边的元素再次进行快速排序
        quickSort(arr,i,start-1);
        //对基准数右边的元素再次进行快速排序
        quickSort(arr,start+1,j);

    }
}
